package com.ting.test.algorithms.二叉树;

import java.util.Stack;

public class 非递归遍历 {

    public static void main(String[] args) {

        xianxu(new TreeNode(3));
        zhongxu(new TreeNode(3));
        houxu(new TreeNode(3));
    }

    /**
     * 头 左 右
     *
     * @param head
     */
    private static void xianxu(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            System.out.println(pop.val);
            if (pop.right != null) {
                stack.push(pop.right);
            }

            if (pop.left != null) {
                stack.push(pop.left);
            }

        }

    }


    /**
     * 左 头 右
     *
     * @param current
     */
    private static void zhongxu(TreeNode current) {
        if (current == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(current);
        while (!stack.isEmpty() || current != null) {
            if (current.left != null) {
                stack.push(current.left);//先将左子树依次入栈
                current = current.left;
            } else {// 当左子树为空时，弹出节点并打印，同时开始遍历右子树
                TreeNode pop = stack.pop();
                System.out.println(pop.val);
                current = current.right;
            }
        }
    }

    /**
     * 左 右 头
     *
     * @param head
     */
    private static void houxu(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack();
        Stack<TreeNode> stack2 = new Stack();
        stack.push(head);

        /**
         *
         */
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            stack2.push(pop);//这个循环弹出的顺序是 头 右 左  存入另一个栈 中 逆序打印 就是左 右 头
            System.out.println(pop.val);
            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }

        }


        while (!stack2.isEmpty()) {
            System.out.println(head.val);
        }


    }


}
